package graph

import "container/list"

// Graph 邻接链表存储图
type Graph struct {
	adj []*list.List // 邻接表
	v   int          // 顶点个数
}

// v 表示顶点个数

func NewGraph(v int) *Graph {
	graph := &Graph{
		adj: make([]*list.List, v),
		v:   v,
	}
	for i := range graph.adj {
		graph.adj[i] = list.New()
	}
	return graph
}

// 单边关系表示有向图，添加双边关系表示无向图
// s ,t 表示顶点编号

func (graph *Graph) AddEdge(s, t int) {
	// 邻接表存储
	graph.adj[s].PushBack(t) // t->s
	graph.adj[t].PushBack(s) // s->t
}

// 广度搜索从s到t的最短路径 Breadth first
// s ,t 表示顶点编号
// s-->t  从s顶点走到t顶点
// 广度优先搜索的策略是 先遍历距离起始点最近的全部节点，然后遍历第二层

func (graph *Graph) BFS(src, dist int) []int {
	// 从A 到 A
	if src == dist {
		return nil
	}
	var paths = make([]int, 0)

	// 初始prev 长度为图的顶点个数
	// 为什么遍历记录的是prev?
	// 这是因为通过指向上一个顶点的记法可以方便我们回溯到起点 a <- b <- c <- d(当前节点)可以有效规避岔路

	var prev = make([]int, graph.v)
	for i := range prev {
		prev[i] = -1
	}

	// 通过queue搜索图
	var queue []int
	var visited = make([]bool, graph.v) // 记录节点是否已访问到，过滤重复访问
	var isFound bool
	// 将起点加入队列
	queue = append(queue, src)
	// 标记起点为已访问
	visited[src] = true
	for len(queue) > 0 && !isFound { // 继续搜索的条件是 1 待访问队列不为空 且2还没有找到路径
		// 从搜索队列中取出起始顶点 cur
		cur := queue[0]
		queue = queue[1:]          // 更新queue
		linkList := graph.adj[cur] // 从邻接表中取出 该顶点所在list（也就是该顶点能否访达的顶点）
		// linkList 表示当前起始顶点可以到达的下一个路径
		for e := linkList.Front(); e != nil; e = e.Next() {
			next := e.Value.(int)
			// 判断当前待访问节点是否已经访问过
			if !visited[next] {
				// 从cur能访问到next；cur-->next
				prev[next] = cur
				// 如果 next==dist 说明已经到达目标顶点
				if next == dist {
					isFound = true
					break
				}
				// 如果还没有达到目的节点
				// 将next 添加到待访问队列中
				queue = append(queue, next)
				// 标记k已经被访问过
				visited[next] = true
			}
		}
	}

	if isFound {
		graph.getPathByPrev(prev, src, dist, &paths)
	}
	return paths
}

// 深度优先搜索，思路更简单
// 深度优先的策略是 从当前节点选取一个可达到的节点next，然后从这个节点next继续往下，直到到达终点退出或走不通则向上返回一个节点继续遍历

func (graph *Graph) DFS(s, t int) []int {
	// 初始前驱列表
	var prev = make([]int, graph.v)
	for i := range prev {
		prev[i] = -1
	}
	var visited = make([]bool, graph.v)
	var isFound = new(bool)
	*isFound = false
	var paths = make([]int, 0)

	// 标记s为已经访问
	visited[s] = true

	// 深度搜索从s --->t的路径
	graph.recurseFind(s, t, prev, visited, isFound)

	if *isFound {
		graph.getPathByPrev(prev, s, t, &paths)
	}
	return paths
}

func (graph *Graph) recurseFind(s, t int, prev []int, visited []bool, isFound *bool) {
	if *isFound { // 已经到达
		return
	}
	if s == t { // 已经达到
		*isFound = true
		return
	}

	visited[s] = true
	// 从邻接表中取出s点的可到达路径列表
	linkList := graph.adj[s]

	for e := linkList.Front(); e != nil; e = e.Next() {
		next := e.Value.(int)
		// 如果下一个节点next 还没有访问过
		if !visited[next] {
			prev[next] = s // 标记 s-->next
			// 从s -->t 等价于 已知s-->next  继续搜索next-->t
			// 递归搜索从 next -->t 的路径
			graph.recurseFind(next, t, prev, visited, isFound)
		}
	}
}

func (graph *Graph) getPathByPrev(prev []int, s, t int, paths *[]int) *[]int {
	// s和t是同一个节点，以为着到达目的地
	// t为起始顶点
	if prev[t] == -1 || t == s {
		*paths = append(*paths, t)
	} else {
		// 假设记录的路径prev是：a <- b <- c <- d
		// 那么从d回到a的路径等价于从c回到a再加上d ===递归的思路
		graph.getPathByPrev(prev, s, prev[t], paths)
		*paths = append(*paths, t)
	}
	return paths
}
